package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printLevelOrder2

/**
 * https://leetcode.cn/problems/add-one-row-to-tree/description
 *
 * ```
 * 623. 在二叉树中增加一行
 * 给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。
 * 注意，根节点 root 位于深度 1 。
 * 加法规则如下:
 * 给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
 * cur 原来的左子树应该是新的左子树根的左子树。
 * cur 原来的右子树应该是新的右子树根的右子树。
 * 如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 *
 * 示例 1:
 * 输入: root = [4,2,6,3,1,5], val = 1, depth = 2
 * 输出: [4,1,1,2,null,null,6,3,1,5]
 *
 * 示例 2:
 * 输入: root = [4,2,null,3,1], val = 1, depth = 3
 * 输出:  [4,2,null,1,1,3,null,null,1]
 *
 * 提示:
 * 节点数在 [1, 104] 范围内
 * 树的深度在 [1, 104]范围内
 * -100 <= Node.val <= 100
 * -105 <= val <= 105
 * 1 <= depth <= the depth of tree + 1
 *
 * ```
 */
class leetcode_623 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val root: TreeNode = n4
        n4.left = n2
        n4.right = n6
        n2.left = n3
        n2.right = n1
        n6.left = n5
        val actual = addOneRow(root, 1, 2)
        val expected = arrayListOf(4, 1, 1, 2, null, null, 6, 3, 1, 5)
        Assert.assertEquals(expected.toString(), printLevelOrder2(actual).toString())
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root: TreeNode = n4
        n4.left = n2
        n2.left = n3
        n2.right = n1
        val actual = addOneRow(root, 1, 3)
        val expected = arrayListOf(4, 2, null, 1, 1, 3, null, null, 1)
        Assert.assertEquals(expected.toString(), printLevelOrder2(actual).toString())
    }

    private fun addOneRow(root: TreeNode?, `val`: Int, depth: Int): TreeNode? {
        /**
        题型： 二叉树的前序遍历
        思路：
        有三种情况：
        情况1:root 为空，depth = 1，则 新建root节点并返回，若为空，depth != 1,则返回空
        情况2:root非空，depth = 1，则新建root节点，旧root作为左子树，返回新root节点
        情况3:root非空，depth > 1，
        若(current depth + 1) < depth时，继续遍历
        若(current depth + 1) = depth时，找到了要插入的位置，则新建左右节点，作为当前节点的新左右节点
        若(current depth + 1) > depth时，说明depth 不合法
         */

        // 情况1:root 为空，depth = 1 和 非1
        if (root == null) {
            if (depth == 1) {
                val node: TreeNode = TreeNode(`val`)
                return node
            } else {
                return null
            }
        }

        // 情况2:root非空，depth = 1
        if (depth == 1) {
            val node: TreeNode = TreeNode(`val`)
            node.left = root
            return node
        }


        // 情况3:root非空，depth > 1
        f(root, `val`, depth, 1)
        return root
    }

    private fun f(root: TreeNode?, `val`: Int, depth: Int, currentDepth: Int) {
        // 1 确认函数参数以及返回值
        // 2 确认终止条件
        // 当前节点为空，返回
        if (root == null) {
            return
        }
        // 若(current depth + 1) > depth时，说明depth 不合法
        if ((currentDepth + 1) > depth) {
            return
        }

        // 3 确认单层递归的逻辑：中左右
        // 中
        // 若(current depth + 1) = depth时，找到了要插入的位置，则新建左右节点，作为当前节点的新左右节点
        if ((currentDepth + 1) == depth) {
            val leftNode = TreeNode(`val`)
            leftNode.left = root.left
            root.left = leftNode

            val rightNode = TreeNode(`val`)
            rightNode.right = root.right
            root.right = rightNode
            return
        }
        // 左
        f(root.left, `val`, depth, currentDepth + 1)

        // 右
        f(root.right, `val`, depth, currentDepth + 1)
    }
}